package com.company.ljh.medium;

import com.company.ljh.utils.TreeNode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @description:
 * 236. 二叉树的最近公共祖先
 * 中等
 * 2.3K
 * 相关企业
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
 *
 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2023/7/4 18:37
 * @version:1.0
 */
public class 二叉树的最近公共祖先 {
    /**
     * 后序遍历，当第一次出现左子树发现p或q且右子树发现p或q，或者当前节点发现p或q，则当前节点为最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> result = new ArrayList();
        checkIsExist(root,result,p,q);
        return result.get(0);
    }
    public boolean checkIsExist(TreeNode root,List<TreeNode> result,TreeNode p, TreeNode q){
        if(root == null || !result.isEmpty()){
            return false;
        }
        boolean isThis = (root.val==p.val) || (root.val==q.val);
        boolean leftExist = checkIsExist(root.left,result,p,q);
        boolean rightExist = checkIsExist(root.right,result,p,q);
        if(((isThis&&leftExist) || (isThis&&rightExist) || (leftExist&&rightExist)) &&  result.isEmpty()){
            result.add(root);
        }
        return isThis||rightExist||leftExist;
    }
}
